#define _CRT_SECURE_NO_WARNINGS 



/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* NewHead, * NewTail;
    NewHead = NewTail = NULL;
    ListNode* pcur = head;
    while (pcur)
    {
        if (pcur->val != val)
        {
            if (NewHead == NULL)
            {
                NewHead = NewTail = pcur;
            }
            else
            {
                NewTail->next = pcur;
                NewTail = NewTail->next;
            }
        }
        pcur = pcur->next;
    }
    if (NewHead)
        NewTail->next = NULL;
    return NewHead;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* lesshead, * lesstail;
        lesstail = lesshead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* greaterhead, * greatertail;
        greatertail = greaterhead = (ListNode*)malloc(sizeof(ListNode));
        ListNode* pcur = pHead;
        while (pcur)
        {
            if (pcur->val < x)
            {
                lesstail->next = pcur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail->next = pcur;
                greatertail = greatertail->next;
            }
            pcur = pcur->next;
        }
        greatertail->next = NULL;
        lesstail->next = greaterhead->next;
        ListNode* ret = lesshead->next;
        free(lesshead);
        free(greaterhead);
        lesshead = greaterhead = NULL;
        return ret;
    }
};

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        int arr[900] = { 0 };
        ListNode* pcur = A;
        int i = 0;
        while (pcur)
        {
            arr[i++] = pcur->val;
            pcur = pcur->next;
        }
        int left = 0;
        int right = i - 1;
        while (left < right)
        {
            if (arr[left] != arr[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};